#include "UnlimitedNumber.h"

#include <string>
#include <fstream>
#include <iostream>
#include <cmath>
using namespace std;

UnlimitedNumber::UnlimitedNumber(long long l) : is_positive_(l >= 0)
{
   if(l < 0)
      l = -l;
   data_storage_type :: size_type size = 0;
   for(long long i = l; i != 0; i /= impossible_value)
      ++size;
   if(size == 0)
   {
      is_positive_ = true;
   }
   else
   {
      data_.resize(size, 0);
      for(size_t i = 0; i < size; ++i, l/=impossible_value)
         data_[i] = l % impossible_value;
   }
}

std :: istream & UnlimitedNumber :: operator >> (istream & is)
{
   string str;
   is >> str;
   (*this) = (UnlimitedNumber)str; 
   return is;
}

UnlimitedNumber::UnlimitedNumber(const char * cstr) : is_positive_(cstr[0] != '-')
{*this = (UnlimitedNumber)(string)cstr;}

//VL better to use constructor for const char* here (not to do redundant memory allocation)
//SNMA: it is more comfortable to me to use std::string instaead of char*. And I also need an editable copy of incoming line.
UnlimitedNumber::UnlimitedNumber(string str) : is_positive_(str[0] != '-')
{
   if(str[0]=='+' || str[0] == '-')
      str.erase(0,1); 

   data_storage_type :: size_type size = (str.length() / step) + ((str.length() % step != 0) ? 1 : 0);
   
   data_.resize(size, 0);
   for(size_t i = 0; i < size; ++i)
   {
      for(long long j = step - 1; j >= 0; --j)
      {
         data_[i] *= 10;
         if(str.length()-j != 0)
            data_[i] += str[str.length() - 1 - j] - '0';
      }
      str.erase((str.length() >= step)?(str.length() - step) : 0, step);
   }
   actualize_size();
}

UnlimitedNumber::UnlimitedNumber(const UnlimitedNumber & n) : is_positive_(n.is_positive_)
{
   data_ = n.data_;
}


void UnlimitedNumber::swap(UnlimitedNumber & n)
{
   std::swap(data_, n.data_);
   std::swap(is_positive_, n.is_positive_);
}

UnlimitedNumber & UnlimitedNumber::operator = (UnlimitedNumber const & n)
{
   if(this != &n)
      UnlimitedNumber(n).swap(*this);
   return * this;
}

long long UnlimitedNumber :: get_incorrect_data_num(data_storage_type const & data)
{
   for(data_storage_type :: size_type i = 0; i < data.size(); ++i)
      if(data[i] >= impossible_value)
         return i;
   return -1;
}

// VL better to write separate function for sum and sub
//SNMA: Для хорошего стиля программирования - пожалуй.
UnlimitedNumber & UnlimitedNumber::operator += (const UnlimitedNumber & n)
{
   data_storage_type :: size_type new_size = 0;
   data_storage_type new_data;
   bool new_positivity = true;
   if(is_positive_ == n.is_positive_)
   {
      new_size = 1 + (data_.size() > n.data_.size() ? data_.size() : n.data_.size());
      new_data.resize(new_size, 0);
      for(data_storage_type :: size_type k = 0; k < new_size; ++k) //Решил не переписывать этот циклс итераторами.
      {
         if(k < data_.size())
            new_data[k] += data_[k];
         if(k < n.data_.size())
            new_data[k] += n.data_[k];
         if(k > 0 && new_data[k-1] >= impossible_value)
         {
            ++new_data[k];
            new_data[k-1] -= impossible_value;
         }
      }
      new_positivity = is_positive_;
   }
   else // Если разные знаки
   {
      if(*this == n) // Если они равны по модулю (и с разным знаком, см. выше)
      {
         new_size = 0;
         new_positivity = true;
      }
      else
      {
         UnlimitedNumber const * biggest_abs = 0, * smallest_abs = 0; // Найдём больший и меньший по модулю
         if((*this > -n) == (this->is_positive_) ) // Если this либо положительный и больше модуля n, либо отрицательный и меньше (с учётом знака)
         {
            biggest_abs = this;
            smallest_abs = &n;
         }
         else
         {
            biggest_abs = &n;
            smallest_abs = this;
         }
         new_size = biggest_abs->data_.size();
         new_data = biggest_abs->data_;
         for(size_t i = 0;  i < smallest_abs->data_.size(); ++i)
            new_data[i] -= smallest_abs->data_[i];
         long long err;
         while( (err = get_incorrect_data_num(new_data)) != -1 )
         {
            new_data[err] += impossible_value;
            -- (new_data[err + 1]);
         }

         new_positivity = biggest_abs->is_positive_;
      }
   }
   data_ = new_data;
   is_positive_ = new_positivity;
   actualize_size();
   return * this;
}

UnlimitedNumber & UnlimitedNumber::operator -= (const UnlimitedNumber & n)
{
   return (*this)+=(-n);
}

bool UnlimitedNumber::is_zero()const
{
   return (data_.size() == 0);
}

bool UnlimitedNumber::is_even()const
{
   //VL use "return condition" instead of "return condition ? true : false"
   //SNMA: OK.
   return is_zero() || (data_[0]%2 == 0);
}

UnlimitedNumber & UnlimitedNumber::divide_in_half() //Деление надвое
{
   if(!is_zero())
   {
      data_[0] >>= 1;
      for(data_storage_type :: iterator it = data_.begin() + 1; it != data_.end(); ++it)
      {
         if((*it) % 2)
            *(it - 1) += impossible_value/2;
         (*it) >>= 1;
      }
      actualize_size();
   }
   return *this;
}

UnlimitedNumber & UnlimitedNumber::redouble() //Удвоение
{
   if( !is_zero() && (*(data_.end()-1)) >= impossible_value / 2) // Если при удвоении получилось бы слишком большое число, не вписывающееся в ячейку
      resize(data_.size() + 1);
   
   //VL why are you moving from most significant to least significant bit?
   //VL it could give mistake if multiplying on smth more than 2
   //SNMA: 1. А какая разница, если этот код data_storage_type :: size_type newsize_нужен, по сути, только для побитового сдвига влево на 1 бит?
   //SNMA: 2. Не "multiplying on smth more than 2", а (если оставить тот код, который был во время вашей проверки, а сейчас заменён единицей)

   for(data_storage_type :: iterator it = data_.end() - 1; it >= data_.begin(); --it)
   {
      *it <<= 1;
      if(*it >= impossible_value)
      {
         *(it + 1) += 1; //или "+= data_[i] / impossible_value" - но это всегда равно единице (меньше быть не может из-за if'а, больше - т.к. всего лишь удваевали).
         *it %= impossible_value;
      }
   }
   return *this;
}

UnlimitedNumber & UnlimitedNumber::unsigned_multiply(UnlimitedNumber & n) const    // Функция работает по тому алгоритму, что давали нам на алгоритмах (или на плюсах... Но точно в AMSE). Не зря ведь давали?
{
   //VL strange algorithm, it has the same complexity as usual long multiplication 

   //SNMA: Нам давали его в AMSE, причём доказывали вроде, что он лучше кучи сложений, при условии, что битовые сдвиги нам будут дешевле сложений. Возможно, тут выгода не столь большая, но она всё же (надеюсь) присутствует.
/*
SNMA: идея в том, что вместо 15*10 = 15+15+15+15+15+15+15+15+15+15
мы вычисляем 15*10 = (15*5)<<1, где 15*5 = ((15*2)<<1) + 15, где 15*2 = 15<<1
В результате получается быстрее.
*/

   if(n.is_zero())
      return n;
   else
   {
      bool is_n_even = n.is_even();
      UnlimitedNumber & answ = unsigned_multiply(n.divide_in_half());
      answ.redouble();
      if(! is_n_even ) //Если умножаем на нечётное
         answ+=(*this);
      return answ;
   }
}

UnlimitedNumber & UnlimitedNumber::operator *= (UnlimitedNumber n)
{
   bool new_sign = (n.is_positive_ == is_positive_);
   *this = unsigned_multiply(n);
   is_positive_ = new_sign;
   return *this;
}

UnlimitedNumber & UnlimitedNumber::operator /= (const UnlimitedNumber & n)
{
   (*this) = (*this) / n;
   return *this;
}

void UnlimitedNumber::resize(UnlimitedNumber :: data_storage_type :: size_type new_size)
{
   data_.resize(new_size);
}

void UnlimitedNumber::actualize_size()
{
   data_storage_type :: size_type new_size = data_.size();
   while(new_size != 0 && data_[new_size - 1] == 0)
      --new_size;
   resize(new_size);
}

string UnlimitedNumber :: get()const
{
   string answ;
   if(! is_zero())
   {
      const long long k = (long long) (pow(10, double(step - 1)));
      for(long long i = data_.size() - 1, j = k; i >= 0 ; --i, j = k)
      {
         while(j >= 1)
         {
            answ += '0' + (data_[i] / j)%(10*j);
            j/=10;
         }
      }
      while(answ[0] == '0')
         answ.erase(0,1);
      if(!is_positive_)
         answ = '-' + answ;
   }
   else
      answ = "0";
   return answ;
}

// VL is not correct, you don't compare positivity 
//SNMA: Исправил.
bool operator == (UnlimitedNumber const & a, UnlimitedNumber const & b)
{
   if((a.data_.size() != b.data_.size()) || (a.is_positive_ == b.is_positive_) )
      return false;
   else
   {
      for(UnlimitedNumber :: data_storage_type :: const_iterator ia = a.data_.begin(), ib = b.data_.begin(); ia != a.data_.end(); ++ia, ++ib)
         if(*ia != *ib)
            return false;
   }
   return true;
}


bool operator != (UnlimitedNumber const & a, UnlimitedNumber const & b)
{ return !(a == b); }

bool operator < (UnlimitedNumber const & a, UnlimitedNumber const & b)
{
   bool answ = false;
   if(a != b)
   {
      if(a.is_positive_ != b.is_positive_)
         return b.is_positive_;
      else
      {
         if(a.data_.size() != b.data_.size())
         {
            if(a.data_.size() < b.data_.size())
               answ = true;
            else
               answ = false;
         }
         else
         {
            size_t size = a.data_.size();
            long long i;
            for(i = size - 1; i >= 0; --i)
               if(a.data_[i] != b.data_[i])
               {
                  if(a.data_[i] < b.data_[i])
                     answ =  true;
                  else
                     answ = false;
                  break;
               }
            if(i < 0)
               answ = false; // Если равны по модулю
         }
         if(!a.is_positive_)
            answ = !answ;
      }
   }
   return answ;
}

bool operator > (UnlimitedNumber const & a, UnlimitedNumber const & b)
{
   return b<a;
}

bool operator <= (UnlimitedNumber const & a, UnlimitedNumber const & b)
{ return !(a>b); }

bool operator >= (UnlimitedNumber const & a, UnlimitedNumber const & b)
{ return !(a<b); }

UnlimitedNumber operator + (UnlimitedNumber a, UnlimitedNumber const & b)
{ return a += b; }

UnlimitedNumber operator - (UnlimitedNumber a, UnlimitedNumber const & b)
{ return a -= b; }

UnlimitedNumber operator * (UnlimitedNumber a, UnlimitedNumber const & b)
{ return a *= b; }

UnlimitedNumber operator / (UnlimitedNumber a, UnlimitedNumber b)
{
   if (b.is_zero())
      throw "invalid";
   bool sign = (a.is_positive_ == b.is_positive_);
   b.is_positive_ = a.is_positive_ = true;
   UnlimitedNumber answ;
   for(; a >= b; answ+=1)
      a -= b;
   answ.is_positive_ = sign;
   return answ;
}

std::ostream & operator << (std::ostream & ostr, UnlimitedNumber const & n)
{
   ostr<< n.get();
   return ostr;
}

UnlimitedNumber operator - (UnlimitedNumber n)
{
   n.is_positive_ = ! n.is_positive_;
   return n;
}
